package List$Stack$queue;
import common.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 判断链表中是否有环，并且找到入环的起点
 */
public class LinkedListCycleII {
    /**
     * 先利用快慢指针法判断链表是否有环，
     * 如果有环，则慢指针从头开始，快指针从相遇出开始，每次走一步，再次相遇即入环点
     * @param head 链表头
     * @return 入环的起点
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //快慢指针找相遇点
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) break;
        }
        // 判断是否有环
        if (fast != null && fast.next != null){
            slow = head;
            while (slow != fast){
                slow = slow.next;
                fast = fast.next;
                if (slow == fast) return slow;
            }
            return slow;
        }
        return null;
    }

    /**
     * 找环的第二种方法，使用Set集合
     * 因为Set集合在添加元素之前，会先判断集合中是否已经存在该元素，
     * 因此当遇到的第一个已经存在的元素，就是环的起点
     * @param head 链表头
     * @return 入环的起点
     */
    public ListNode detectCycleII(ListNode head) {
        if (head == null || head.next == null) return null;
        Set<ListNode> nodes = new HashSet<>();
        while (head != null){
            if (!nodes.add(head)){
                return head;
            }
            head = head.next;
        }
        return null;
    }
}
